package com.kevin.algorithm;

import com.kevin.model.Location;
import com.kevin.utils.DistanceUtil;
import com.kevin.utils.MapUtils;
import com.kevin.utils.PointsRep;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;

/**
 * @Description: 多点连线不相交算法
 * 该算法指定了起止点
 *
 * @author kevin
 * @version V1.0
 * @date 2019/2/22 11:08
 **/
public class MultipointRoute implements AlgorithmStrategy{
    private static final Logger LOGGER = LoggerFactory.getLogger(MultipointRoute.class);

    private BigDecimal shortestDis = new BigDecimal(-1);
    private List<Location> bestRoute;

    @Override
    public Location[][] execute(PointsRep pointsRep) {
        List<Location> sortedList = new ArrayList<>();
        List<Location> unSortedList = new ArrayList<>();

        List<Location> originList = pointsRep.getPoints();

        if(originList.size()>1 && pointsRep.getBegin()!=null && pointsRep.getEnd()!=null){
            /**
             * 封装起止点
             */
            sortedList.add(pointsRep.getBegin());
            sortedList.add(pointsRep.getEnd());

            for(int i=0;i<originList.size();i++){
                unSortedList.add(originList.get(i));
            }

            /**
             * 调用多点连线不相交算法
             */
            LOGGER.info("多点连线不相交算法开始");
            getBestRoute(sortedList,unSortedList);
            LOGGER.info("多点连线不相交算法结束");
        }

        /**
         * 将队列移除起止点后封装成二维数组返回
         */
        bestRoute.remove(0);
        bestRoute.remove(bestRoute.size()-1);
        Location[][] locations = new Location[1][bestRoute.size()];
        for(int i=0;i<bestRoute.size();i++){
            locations[0][i] = bestRoute.get(i);
        }

        return locations;
    }

    /**
     * 通过两点插入距离最短算法计算
     */
    private void getBestRoute(List<Location> sortedList,List<Location> unSortedList){
        if(unSortedList.size()>0){
            /**
             * 获取已排序列表相邻两点的中心点
             */
            List<Location> centerPoints = new ArrayList<>();
            for(int i=1;i<sortedList.size();i++){
                List<Location> tempList = new ArrayList<>();
                tempList.add(sortedList.get(i-1));
                tempList.add(sortedList.get(i));
                Location center = MapUtils.getCenterPoint(tempList);
                centerPoints.add(center);
            }

            int unsortedIndex = -1;
            int centerIndex = -1;
            BigDecimal currDis = new BigDecimal(-1);

            for(int i=0;i<unSortedList.size();i++){
                for(int j=0;j<centerPoints.size();j++){
                    BigDecimal tempDis = BigDecimal.valueOf(Double.valueOf(DistanceUtil.algorithm(unSortedList.get(i).getLon(),unSortedList.get(i).getLat(),centerPoints.get(j).getLon(),centerPoints.get(j).getLat())));
                    if(currDis.compareTo(new BigDecimal(-1)) == 0 || currDis.compareTo(tempDis) == 1 ){
                        unsortedIndex = i;
                        centerIndex = j;
                        currDis = tempDis;
                    }
                }
            }

            Location change = unSortedList.get(unsortedIndex);
            sortedList.add(centerIndex+1,change);
            unSortedList.remove(unsortedIndex);


            /**
             * 递归调用本方法
             */
            getBestRoute(sortedList,unSortedList);
        }else{
            bestRoute = sortedList;
        }
    }
}
